package com.c2b.algorithm.leetcode.base;

/**
 * <a href='https://leetcode.cn/problems/verifying-an-alien-dictionary/'>验证外星语词典(Verifying an Alien Dictionary)</a>
 * <p>某种外星语也使用英文小写字母，但可能顺序 order 不同。字母表的顺序（order）是一些小写字母的排列。</p>
 * <p>给定一组用外星语书写的单词 words，以及其字母表的顺序 order，只有当给定的单词在这种外星语中按字典序排列时，返回 true；否则，返回 false。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
 *      输出：true
 *      解释：在该语言的字母表中，'h' 位于 'l' 之前，所以单词序列是按字典序排列的。
 *
 * 示例 2：
 *      输入：words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz"
 *      输出：false
 *      解释：在该语言的字母表中，'d' 位于 'l' 之后，那么 words[0] > words[1]，因此单词序列不是按字典序排列的。
 *
 * 示例 3：
 *      输入：words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz"
 *      输出：false
 *      解释：当前三个字符 "app" 匹配时，第二个字符串相对短一些，然后根据词典编纂规则 "apple" > "app"，因为 'l' > '∅'，其中 '∅' 是空白字符，定义为比任何其他字符都小（更多信息）。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *     <ul>
 *         <li>1 <= words.length <= 100</li>
 *         <li>1 <= words[i].length <= 20</li>
 *         <li>order.length == 26</li>
 *         <li>在 words[i] 和 order 中的所有字符都是英文小写字母。</li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/12/19 11:48
 */
public class LC0953VerifyingAlienDictionary_S {
    static class Solution {
        public boolean isAlienSorted(String[] words, String order) {
            int[] orderArr = new int[26];
            for (int i = 0; i < 26; i++) {
                orderArr[order.charAt(i) - 'a'] = i;
            }
            for (int i = 0; i < words.length - 1; i++) {
                if (!check(words[i], words[i + 1], orderArr)) {
                    return false;
                }
            }
            return true;
        }

        private boolean check(String word1, String word2,int[] orderArr) {
            int word1Len = word1.length();
            int word2Len = word2.length();
            for (int i = 0; i < word1Len; i++) {
                // i 位置前的所有字符都相等，此时word1在i位置仍有字符，word2已判断完
                if (word2Len - 1 < i) {
                    return false;
                }
                // differ：用来记录 word1 和 word2 中 i 位置的字符 在order中的位置。
                // differ == 0，位置相同
                // differ < 0 ，word1 中 i 位置字符在order中靠前
                // differ > 0 ，word2 中 i 位置字符在order中靠前
                int diff = orderArr[word1.charAt(i)] - orderArr[word2.charAt(i)];
                if (diff == 0) {
                    continue;
                }
                return diff < 0;
            }
            // 如果 word1 经过了所有的字符，word2 还有剩余字符。则 word1 靠前
            return word1Len <= word2Len;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.isAlienSorted(new String[]{"hello", "leetcode"}, "hlabcdefgijkmnopqrstuvwxyz"));
        System.out.println(solution.isAlienSorted(new String[]{"word","world","row"}, "worldabcefghijkmnpqstuvxyz"));
        System.out.println(solution.isAlienSorted(new String[]{"apple","app"}, "abcdefghijklmnopqrstuvwxyz"));
    }
}
